The present invention relates to managing access to a shared resource in a data processing system.
It is a common programming technique to use software semaphores to serialize access to shared resources, of which examples include printers, tape, disks units, etc., or for example, internal software resources like files, tables, buffers, storage areas in general, and so on.
FIG. 1 shows schematically the components of a semaphore system as known in the prior art. As shown in FIG. 1, the process 110 is in communication with a semaphore module 130, which maintains a set of semaphores, each one with its own queue 141,142, 143, and furthermore acts as an intermediary to communications with one or more shared resources 120.
When the process 110 needs to access the resource 120, it queries the semaphore module 130. If the resource requested 120 is ready (“green”), the semaphore module sets its status to busy (“red”) and the process 110 is accorded control of the shared resource 120. When the process finishes with the resource 120, it releases the resource and the semaphore module returns its status to ready (“green”). If when the query is received the semaphore module's status is busy (“red”), the process 110 is registered inside the semaphore queue 143 corresponding to the resource 120 and its request to access the resource usage is enqueued. When the process 110's enqueued request reaches the head of the queue, the semaphore module sets its status to “green” for that queue element, the waiting process 110 is woken up, and it can use and then release the resource 120, which is then removed from the semaphore queue.
As a side effect of this way of handling the software semaphores, especially in case of heavily used resources, a process has to wait to get its request dispatched and serviced. There are different algorithms to handle the semaphore queue stacks based on different criteria (for example, First-In-First-Out or FIFO, Last-In-First-Out or LIFO, priority, request types, weights, and so forth) but once there is a queue, a process has to wait a greater or lesser amount of time for its turn.
FIG. 2 shows the progress of a request through the queue in the system of FIG. 1. FIG. 2 plots queue position on a horizontal axis, and time on a vertical axis. The total length of the queue at any given time is represented by the shaded area between the axes and the line 215. If a request is issued by the process 110 at a time indicated by the dotted line 205, the request proceeds along the queue in the manner represented by the line 210, and eventually arrives at the head of the queue at the point 220, whereupon the resource 120 becomes available to the process 110.
The article entitled “Semaphore Queue Priority Assignment for Real-Time Multiprocessor Synchronization” published in IEEE Transactions in Software Engineering October 1995 (vol. 21 no. 10) pp. 834-844 by Victor B. Lortz and Kang G. Shin describes work on real-time scheduling with global shared resources in multiprocessor systems that assigns as much blocking as possible to the lowest-priority tasks. In this paper, it is shown that better schedulability can be achieved if global blocking is distributed according to the blocking tolerance of tasks rather than their execution priorities.
US20080244130 describes how, in an ordered semaphore management system, a pending state allows threads not competing for a locked semaphore to bypass one or more threads waiting for the same locked semaphore. The number of pending levels determines the number of consecutive threads vying for the same locked semaphore which can be bypassed. When more than one level is provided, the pending levels are prioritized in the queued order.
The article entitled “Priority Semaphores” from the Oxford Computer Journal, Volume 32, Issue 1 pp. 24-28 by B. Freisleben and J. L. Keedy discusses how neither low-level mechanisms such as semaphores nor higher-level mechanisms such as path expressions provide a simple means of solving synchronisation problems involving the scheduling of processes or classes of processes according to different priorities. This paper presents a new set of primitives which are easy to use and simple to implement. Their use is described in terms of the familiar reader-writer problem and the general scheduling problem involving arbitrary levels of priority with support for pre-emption and shared access by certain process classes. An efficient implementation, which reduces to a minimum the number of calls required to the process scheduler, is then described.